High-level interface
====================

   This interface provides functions for reading and writing `bzip2'
format files.  First, some general points.

   * All of the functions take an `int*' first argument,   `bzerror'.
     After each call, `bzerror' should be consulted first to determine
      the outcome of the call.  If `bzerror' is `BZ_OK',   the call
     completed   successfully, and only then should the return value of
     the function   (if any) be consulted.  If `bzerror' is
     `BZ_IO_ERROR',   there was an error   reading/writing the
     underlying compressed file, and you should   then consult
     `errno'/`perror' to determine the   cause of the difficulty.
     `bzerror' may also be set to various other values; precise details
     are   given on a per-function basis below.

   * If `bzerror' indicates an error   (ie, anything except `BZ_OK' and
     `BZ_STREAM_END'),   you should immediately call `bzReadClose' (or
     `bzWriteClose',   depending on whether you are attempting to read
     or to write)   to free up all resources associated   with the
     stream.  Once an error has been indicated, behaviour of all calls
     except `bzReadClose' (`bzWriteClose') is undefined.    The
     implication is that (1) `bzerror' should   be checked after each
     call, and (2) if `bzerror' indicates an error,   `bzReadClose'
     (`bzWriteClose') should then be called to clean up.

   * The `FILE*' arguments passed to    `bzReadOpen'/`bzWriteOpen'
     should be set to binary mode.    Most Unix systems will do this by
     default, but other platforms,   including Windows and Mac, will
     not.  If you omit this, you may   encounter problems when moving
     code to new platforms.

   * Memory allocation requests are handled by   `malloc'/`free'.    At
     present   there is no facility for user-defined memory allocators
     in the file I/O   functions (could easily be added, though).

`bzReadOpen'
------------

        typedef void BZFILE;

        BZFILE *bzReadOpen ( int *bzerror, FILE *f,
                             int small, int verbosity,
                             void *unused, int nUnused );
   Prepare to read compressed data from file handle `f'.  `f' should
refer to a file which has been opened for reading, and for which the
error indicator (`ferror(f)')is not set.  If `small' is 1, the library
will try to decompress using less memory, at the expense of speed.

   For reasons explained below, `bzRead' will decompress the `nUnused'
bytes starting at `unused', before starting to read from the file `f'.
At most `BZ_MAX_UNUSED' bytes may be supplied like this.  If this
facility is not required, you should pass `NULL' and `0' for `unused'
and n`Unused' respectively.

   For the meaning of parameters `small' and `verbosity', see
`bzDecompressInit'.

   The amount of memory needed to decompress a file cannot be determined
until the file's header has been read.  So it is possible that
`bzReadOpen' returns `BZ_OK' but a subsequent call of `bzRead' will
return `BZ_MEM_ERROR'.

   Possible assignments to `bzerror':
           `BZ_PARAM_ERROR'
              if `f' is `NULL'
              or `small' is neither `0' nor `1'
              or `(unused == NULL && nUnused != 0)'
              or `(unused != NULL && !(0 <= nUnused <= BZ_MAX_UNUSED))'
           `BZ_IO_ERROR'
              if `ferror(f)' is nonzero
           `BZ_MEM_ERROR'
              if insufficient memory is available
           `BZ_OK'
              otherwise.

   Possible return values:
           Pointer to an abstract `BZFILE'
              if `bzerror' is `BZ_OK'
           `NULL'
              otherwise

   Allowable next actions:
           `bzRead'
              if `bzerror' is `BZ_OK'
           `bzClose'
              otherwise

`bzRead'
--------

        int bzRead ( int *bzerror, BZFILE *b, void *buf, int len );
   Reads up to `len' (uncompressed) bytes from the compressed file `b'
into the buffer `buf'.  If the read was successful, `bzerror' is set to
`BZ_OK' and the number of bytes read is returned.  If the logical
end-of-stream was detected, `bzerror' will be set to `BZ_STREAM_END',
and the number of bytes read is returned.  All other `bzerror' values
denote an error.

   `bzRead' will supply `len' bytes, unless the logical stream end is
detected or an error occurs.  Because of this, it is possible to detect
the stream end by observing when the number of bytes returned is less
than the number requested.  Nevertheless, this is regarded as
inadvisable; you should instead check `bzerror' after every call and
watch out for `BZ_STREAM_END'.

   Internally, `bzRead' copies data from the compressed file in chunks
of size `BZ_MAX_UNUSED' bytes before decompressing it.  If the file
contains more bytes than strictly needed to reach the logical
end-of-stream, `bzRead' will almost certainly read some of the trailing
data before signalling `BZ_SEQUENCE_END'.  To collect the read but
unused data once `BZ_SEQUENCE_END' has appeared, call `bzReadGetUnused'
immediately before `bzReadClose'.

   Possible assignments to `bzerror':
           `BZ_PARAM_ERROR'
              if `b' is `NULL' or `buf' is `NULL' or `len < 0'
           `BZ_SEQUENCE_ERROR'
              if `b' was opened with `bzWriteOpen'
           `BZ_IO_ERROR'
              if there is an error reading from the compressed file
           `BZ_UNEXPECTED_EOF'
              if the compressed file ended before the logical end-of-stream was detected
           `BZ_DATA_ERROR'
              if a data integrity error was detected in the compressed stream
           `BZ_DATA_ERROR_MAGIC'
              if the stream does not begin with the requisite header bytes (ie, is not
              a `bzip2' data file).  This is really a special case of `BZ_DATA_ERROR'.
           `BZ_MEM_ERROR'
              if insufficient memory was available
           `BZ_STREAM_END'
              if the logical end of stream was detected.
           `BZ_OK'
              otherwise.

   Possible return values:
           number of bytes read
              if `bzerror' is `BZ_OK' or `BZ_STREAM_END'
           undefined
              otherwise

   Allowable next actions:
           collect data from `buf', then `bzRead' or `bzReadClose'
              if `bzerror' is `BZ_OK'
           collect data from `buf', then `bzReadClose' or `bzReadGetUnused'
              if `bzerror' is `BZ_SEQUENCE_END'
           `bzReadClose'
              otherwise

`bzReadGetUnused'
-----------------

        void bzReadGetUnused ( int* bzerror, BZFILE *b,
                               void** unused, int* nUnused );
   Returns data which was read from the compressed file but was not
needed to get to the logical end-of-stream.  `*unused' is set to the
address of the data, and `*nUnused' to the number of bytes.  `*nUnused'
will be set to a value between `0' and `BZ_MAX_UNUSED' inclusive.

   This function may only be called once `bzRead' has signalled
`BZ_STREAM_END' but before `bzReadClose'.

   Possible assignments to `bzerror':
           `BZ_PARAM_ERROR'
              if `b' is `NULL'
              or `unused' is `NULL' or `nUnused' is `NULL'
           `BZ_SEQUENCE_ERROR'
              if `BZ_STREAM_END' has not been signalled
              or if `b' was opened with `bzWriteOpen'
          `BZ_OK'
              otherwise

   Allowable next actions:
           `bzReadClose'

`bzReadClose'
-------------

        void bzReadClose ( int *bzerror, BZFILE *b );
   Releases all memory pertaining to the compressed file `b'.
`bzReadClose' does not call `fclose' on the underlying file handle, so
you should do that yourself if appropriate.  `bzReadClose' should be
called to clean up after all error situations.

   Possible assignments to `bzerror':
           `BZ_SEQUENCE_ERROR'
              if `b' was opened with `bzOpenWrite'
           `BZ_OK'
              otherwise

   Allowable next actions:
           none

`bzWriteOpen'
-------------

        BZFILE *bzWriteOpen ( int *bzerror, FILE *f,
                              int blockSize100k, int verbosity,
                              int workFactor );
   Prepare to write compressed data to file handle `f'.  `f' should
refer to a file which has been opened for writing, and for which the
error indicator (`ferror(f)')is not set.

   For the meaning of parameters `blockSize100k', `verbosity' and
`workFactor', see
`bzCompressInit'.

   All required memory is allocated at this stage, so if the call
completes successfully, `BZ_MEM_ERROR' cannot be signalled by a
subsequent call to `bzWrite'.

   Possible assignments to `bzerror':
           `BZ_PARAM_ERROR'
              if `f' is `NULL'
              or `blockSize100k < 1' or `blockSize100k > 9'
           `BZ_IO_ERROR'
              if `ferror(f)' is nonzero
           `BZ_MEM_ERROR'
              if insufficient memory is available
           `BZ_OK'
              otherwise

   Possible return values:
           Pointer to an abstract `BZFILE'
              if `bzerror' is `BZ_OK'
           `NULL'
              otherwise

   Allowable next actions:
           `bzWrite'
              if `bzerror' is `BZ_OK'
              (you could go directly to `bzWriteClose', but this would be pretty pointless)
           `bzWriteClose'
              otherwise

`bzWrite'
---------

        void bzWrite ( int *bzerror, BZFILE *b, void *buf, int len );
   Absorbs `len' bytes from the buffer `buf', eventually to be
compressed and written to the file.

   Possible assignments to `bzerror':
           `BZ_PARAM_ERROR'
              if `b' is `NULL' or `buf' is `NULL' or `len < 0'
           `BZ_SEQUENCE_ERROR'
              if b was opened with `bzReadOpen'
           `BZ_IO_ERROR'
              if there is an error writing the compressed file.
           `BZ_OK'
              otherwise

`bzWriteClose'
--------------

        int bzWriteClose ( int *bzerror, BZFILE* f,
                           int abandon,
                           unsigned int* nbytes_in,
                           unsigned int* nbytes_out );

   Compresses and flushes to the compressed file all data so far
supplied by `bzWrite'.  The logical end-of-stream markers are also
written, so subsequent calls to `bzWrite' are illegal.  All memory
associated with the compressed file `b' is released.  `fflush' is
called on the compressed file, but it is not `fclose''d.

   If `bzWriteClose' is called to clean up after an error, the only
action is to release the memory.  The library records the error codes
issued by previous calls, so this situation will be detected
automatically.  There is no attempt to complete the compression
operation, nor to `fflush' the compressed file.  You can force this
behaviour to happen even in the case of no error, by passing a nonzero
value to `abandon'.

   If `nbytes_in' is non-null, `*nbytes_in' will be set to be the total
volume of uncompressed data handled.  Similarly, `nbytes_out' will be
set to the total volume of compressed data written.

   Possible assignments to `bzerror':
           `BZ_SEQUENCE_ERROR'
              if `b' was opened with `bzReadOpen'
           `BZ_IO_ERROR'
              if there is an error writing the compressed file
           `BZ_OK'
              otherwise

Handling embedded compressed data streams
-----------------------------------------

   The high-level library facilitates use of `bzip2' data streams which
form some part of a surrounding, larger data stream.
   * For writing, the library takes an open file handle, writes
     compressed data to it, `fflush'es it but does not `fclose' it.
     The calling application can write its own data before and after the
     compressed data stream, using that same file handle.

   * Reading is more complex, and the facilities are not as general as
     they could be since generality is hard to reconcile with
     efficiency.  `bzRead' reads from the compressed file in blocks of
     size `BZ_MAX_UNUSED' bytes, and in doing so probably will overshoot
     the logical end of compressed stream.  To recover this data once
     decompression has ended, call `bzReadGetUnused' after the last
     call of `bzRead' (the one returning `BZ_STREAM_END') but before
     calling `bzReadClose'.

   This mechanism makes it easy to decompress multiple `bzip2' streams
placed end-to-end.  As the end of one stream, when `bzRead' returns
`BZ_STREAM_END', call `bzReadGetUnused' to collect the unused data
(copy it into your own buffer somewhere).  That data forms the start of
the next compressed stream.  To start uncompressing that next stream,
call `bzReadOpen' again, feeding in the unused data via the
`unused'/`nUnused' parameters.  Keep doing this until `BZ_STREAM_END'
return coincides with the physical end of file (`feof(f)').  In this
situation `bzReadGetUnused' will of course return no data.

   This should give some feel for how the high-level interface can be
used.  If you require extra flexibility, you'll have to bite the bullet
and get to grips with the low-level interface.

Standard file-reading/writing code
----------------------------------

   Here's how you'd write data to a compressed file:
     FILE*   f;
     BZFILE* b;
     int     nBuf;
     char    buf[ /* whatever size you like */ ];
     int     bzerror;
     int     nWritten;

     f = fopen ( "myfile.bz2", "w" );
     if (!f) {
        /* handle error */
     }
     b = bzWriteOpen ( &bzerror, f, 9 );
     if (bzerror != BZ_OK) {
        bzWriteClose ( b );
        /* handle error */
     }

     while ( /* condition */ ) {
        /* get data to write into buf, and set nBuf appropriately */
        nWritten = bzWrite ( &bzerror, b, buf, nBuf );
        if (bzerror == BZ_IO_ERROR) {
           bzWriteClose ( &bzerror, b );
           /* handle error */
        }
     }

     bzWriteClose ( &bzerror, b );
     if (bzerror == BZ_IO_ERROR) {
        /* handle error */
     }
   And to read from a compressed file:
     FILE*   f;
     BZFILE* b;
     int     nBuf;
     char    buf[ /* whatever size you like */ ];
     int     bzerror;
     int     nWritten;

     f = fopen ( "myfile.bz2", "r" );
     if (!f) {
        /* handle error */
     }
     b = bzReadOpen ( &bzerror, f, 0, NULL, 0 );
     if (bzerror != BZ_OK) {
        bzReadClose ( &bzerror, b );
        /* handle error */
     }

     bzerror = BZ_OK;
     while (bzerror == BZ_OK && /* arbitrary other conditions */) {
        nBuf = bzRead ( &bzerror, b, buf, /* size of buf */ );
        if (bzerror == BZ_OK) {
           /* do something with buf[0 .. nBuf-1] */
        }
     }
     if (bzerror != BZ_STREAM_END) {
        bzReadClose ( &bzerror, b );
        /* handle error */
     } else {
        bzReadClose ( &bzerror );
     }

Utility functions
=================

`bzBuffToBuffCompress'
----------------------

        int bzBuffToBuffCompress( char*         dest,
                                  unsigned int* destLen,
                                  char*         source,
                                  unsigned int  sourceLen,
                                  int           blockSize100k,
                                  int           verbosity,
                                  int           workFactor );
   Attempts to compress the data in `source[0 .. sourceLen-1]' into the
destination buffer, `dest[0 .. *destLen-1]'.  If the destination buffer
is big enough, `*destLen' is set to the size of the compressed data,
and `BZ_OK' is returned.  If the compressed data won't fit, `*destLen'
is unchanged, and `BZ_OUTBUFF_FULL' is returned.

   Compression in this manner is a one-shot event, done with a single
call to this function.  The resulting compressed data is a complete
`bzip2' format data stream.  There is no mechanism for making
additional calls to provide extra input data.  If you want that kind of
mechanism, use the low-level interface.

   For the meaning of parameters `blockSize100k', `verbosity' and
`workFactor',
see `bzCompressInit'.

   To guarantee that the compressed data will fit in its buffer,
allocate an output buffer of size 1% larger than the uncompressed data,
plus six hundred extra bytes.

   `bzBuffToBuffDecompress' will not write data at or beyond
`dest[*destLen]', even in case of buffer overflow.

   Possible return values:
           `BZ_PARAM_ERROR'
              if `dest' is `NULL' or `destLen' is `NULL'
              or `blockSize100k < 1' or `blockSize100k > 9'
              or `verbosity < 0' or `verbosity > 4'
              or `workFactor < 0' or `workFactor > 250'
           `BZ_MEM_ERROR'
              if insufficient memory is available
           `BZ_OUTBUFF_FULL'
              if the size of the compressed data exceeds `*destLen'
           `BZ_OK'
              otherwise

`bzBuffToBuffDecompress'
------------------------

        int bzBuffToBuffDecompress ( char*         dest,
                                     unsigned int* destLen,
                                     char*         source,
                                     unsigned int  sourceLen,
                                     int           small,
                                     int           verbosity );
   Attempts to decompress the data in `source[0 .. sourceLen-1]' into
the destination buffer, `dest[0 .. *destLen-1]'.  If the destination
buffer is big enough, `*destLen' is set to the size of the uncompressed
data, and `BZ_OK' is returned.  If the compressed data won't fit,
`*destLen' is unchanged, and `BZ_OUTBUFF_FULL' is returned.

   `source' is assumed to hold a complete `bzip2' format data stream.
`bzBuffToBuffDecompress' tries to decompress the entirety of the stream
into the output buffer.

   For the meaning of parameters `small' and `verbosity', see
`bzDecompressInit'.

   Because the compression ratio of the compressed data cannot be known
in advance, there is no easy way to guarantee that the output buffer
will be big enough.  You may of course make arrangements in your code to
record the size of the uncompressed data, but such a mechanism is beyond
the scope of this library.

   `bzBuffToBuffDecompress' will not write data at or beyond
`dest[*destLen]', even in case of buffer overflow.

   Possible return values:
           `BZ_PARAM_ERROR'
              if `dest' is `NULL' or `destLen' is `NULL'
              or `small != 0 && small != 1'
              or `verbosity < 0' or `verbosity > 4'
           `BZ_MEM_ERROR'
              if insufficient memory is available
           `BZ_OUTBUFF_FULL'
              if the size of the compressed data exceeds `*destLen'
           `BZ_DATA_ERROR'
              if a data integrity error was detected in the compressed data
           `BZ_DATA_ERROR_MAGIC'
              if the compressed data doesn't begin with the right magic bytes
           `BZ_UNEXPECTED_EOF'
              if the compressed data ends unexpectedly
           `BZ_OK'
              otherwise

`zlib' compatibility functions
==============================

   Yoshioka Tsuneo has contributed some functions to give better `zlib'
compatibility.  These functions are `bzopen', `bzread', `bzwrite',
`bzflush', `bzclose', `bzerror' and `bzlibVersion'.  These functions
are not (yet) officially part of the library.  If they break, you get
to keep all the pieces.  Nevertheless, I think they work ok.
     typedef void BZFILE;

     const char * bzlibVersion ( void );
   Returns a string indicating the library version.
     BZFILE * bzopen  ( const char *path, const char *mode );
     BZFILE * bzdopen ( int        fd,    const char *mode );
   Opens a `.bz2' file for reading or writing, using either its name or
a pre-existing file descriptor.  Analogous to `fopen' and `fdopen'.
     int bzread  ( BZFILE* b, void* buf, int len );
     int bzwrite ( BZFILE* b, void* buf, int len );
   Reads/writes data from/to a previously opened `BZFILE'.  Analogous
to `fread' and `fwrite'.
     int  bzflush ( BZFILE* b );
     void bzclose ( BZFILE* b );
   Flushes/closes a `BZFILE'.  `bzflush' doesn't actually do anything.
Analogous to `fflush' and `fclose'.

     const char * bzerror ( BZFILE *b, int *errnum )
   Returns a string describing the more recent error status of `b', and
also sets `*errnum' to its numerical value.

Using the library in a `stdio'-free environment
===============================================

Getting rid of `stdio'
----------------------

   In a deeply embedded application, you might want to use just the
memory-to-memory functions.  You can do this conveniently by compiling
the library with preprocessor symbol `BZ_NO_STDIO' defined.  Doing this
gives you a library containing only the following eight functions:

   `bzCompressInit', `bzCompress', `bzCompressEnd'
`bzDecompressInit', `bzDecompress', `bzDecompressEnd'
`bzBuffToBuffCompress', `bzBuffToBuffDecompress'

   When compiled like this, all functions will ignore `verbosity'
settings.

Critical error handling
-----------------------

   `libbzip2' contains a number of internal assertion checks which
should, needless to say, never be activated.  Nevertheless, if an
assertion should fail, behaviour depends on whether or not the library
was compiled with `BZ_NO_STDIO' set.

   For a normal compile, an assertion failure yields the message
        bzip2/libbzip2, v0.9.5: internal error number N.
        This is a bug in bzip2/libbzip2, v0.9.5.  Please report
        it to me at: jseward@acm.org.  If this happened when
        you were using some program which uses libbzip2 as a
        component, you should also report this bug to the author(s)
        of that program.  Please make an effort to report this bug;
        timely and accurate bug reports eventually lead to higher
        quality software.  Thanks.  Julian Seward, 24 May 1999.
   where `N' is some error code number.  `exit(3)' is then called.

   For a `stdio'-free library, assertion failures result in a call to a
function declared as:
        extern void bz_internal_error ( int errcode );
   The relevant code is passed as a parameter.  You should supply such
a function.

   In either case, once an assertion failure has occurred, any
`bz_stream' records involved can be regarded as invalid.  You should
not attempt to resume normal operation with them.

   You may, of course, change critical error handling to suit your
needs.  As I said above, critical errors indicate bugs in the library
and should not occur.  All "normal" error situations are indicated via
error return codes from functions, and can be recovered from.

Making a Windows DLL
====================

   Everything related to Windows has been contributed by Yoshioka Tsuneo
(`QWF00133@niftyserve.or.jp' / `tsuneo-y@is.aist-nara.ac.jp'), so you
should send your queries to him (but perhaps Cc: me, `jseward@acm.org').

   My vague understanding of what to do is: using Visual C++ 5.0, open
the project file `libbz2.dsp', and build.  That's all.

   If you can't open the project file for some reason, make a new one,
naming these files: `blocksort.c', `bzlib.c', `compress.c',
`crctable.c', `decompress.c', `huffman.c',
`randtable.c' and `libbz2.def'.  You will also need to name the header
files `bzlib.h' and `bzlib_private.h'.

   If you don't use VC++, you may need to define the proprocessor symbol
`_WIN32'.

   Finally, `dlltest.c' is a sample program using the DLL.  It has a
project file, `dlltest.dsp'.

   If you just want a makefile for Visual C, have a look at
`makefile.msc'.

   Be aware that if you compile `bzip2' itself on Win32, you must set
`BZ_UNIX' to 0 and `BZ_LCCWIN32' to 1, in the file `bzip2.c', before
compiling.  Otherwise the resulting binary won't work correctly.

   I haven't tried any of this stuff myself, but it all looks plausible.

Miscellanea
***********

   These are just some random thoughts of mine.  Your mileage may vary.

Limitations of the compressed file format
=========================================

   `bzip2-0.9.5' and `0.9.0' use exactly the same file format as the
previous version, `bzip2-0.1'.  This decision was made in the interests
of stability.  Creating yet another incompatible compressed file format
would create further confusion and disruption for users.

   Nevertheless, this is not a painless decision.  Development work
since the release of `bzip2-0.1' in August 1997 has shown complexities
in the file format which slow down decompression and, in retrospect,
are unnecessary.  These are:
   * The run-length encoder, which is the first of the
     compression transformations, is entirely irrelevant.        The
     original purpose was to protect the sorting algorithm       from
     the very worst case input: a string of repeated       symbols.
     But algorithm steps Q6a and Q6b in the original
     Burrows-Wheeler technical report (SRC-124) show how       repeats
     can be handled without difficulty in block       sorting.

   * The randomisation mechanism doesn't really need to be       there.
     Udi Manber and Gene Myers published a suffix       array
     construction algorithm a few years back, which       can be
     employed to sort any block, no matter how       repetitive, in O(N
     log N) time.  Subsequent work by       Kunihiko Sadakane has
     produced a derivative O(N (log N)^2)       algorithm which usually
     outperforms the Manber-Myers       algorithm.

     I could have changed to Sadakane's algorithm, but I find       it
     to be slower than `bzip2''s existing algorithm for       most
     inputs, and the randomisation mechanism protects       adequately
     against bad cases.  I didn't think it was       a good tradeoff to
     make.  Partly this is due to the fact       that I was not flooded
     with email complaints about       `bzip2-0.1''s performance on
     repetitive data, so       perhaps it isn't a problem for real
     inputs.

     Probably the best long-term solution,       and the one I have
     incorporated into 0.9.5 and above,       is to use the existing
     sorting       algorithm initially, and fall back to a O(N (log
     N)^2)       algorithm if the standard algorithm gets into
     difficulties.

   * The compressed file format was never designed to be       handled
     by a library, and I have had to jump though       some hoops to
     produce an efficient implementation of       decompression.  It's
     a bit hairy.  Try passing       `decompress.c' through the C
     preprocessor       and you'll see what I mean.  Much of this
     complexity       could have been avoided if the compressed size of
          each block of data was recorded in the data stream.

   * An Adler-32 checksum, rather than a CRC32 checksum,       would be
     faster to compute.  It would be fair to say that the `bzip2'
format was frozen before I properly and fully understood the performance
consequences of doing so.

   Improvements which I was able to incorporate into 0.9.0, despite
using the same file format, are:
   * Single array implementation of the inverse BWT.  This
     significantly speeds up decompression, presumably       because it
     reduces the number of cache misses.

   * Faster inverse MTF transform for large MTF values.  The       new
     implementation is based on the notion of sliding blocks       of
     values.

   * `bzip2-0.9.0' now reads and writes files with `fread'       and
     `fwrite'; version 0.1 used `putc' and `getc'.        Duh!  Well,
     you live and learn.

   Further ahead, it would be nice to be able to do random access into
files.  This will require some careful design of compressed file
formats.

Portability issues
==================

   After some consideration, I have decided not to use GNU `autoconf'
to configure 0.9.5.

   `autoconf', admirable and wonderful though it is, mainly assists
with portability problems between Unix-like platforms.  But `bzip2'
doesn't have much in the way of portability problems on Unix; most of
the difficulties appear when porting to the Mac, or to Microsoft's
operating systems.  `autoconf' doesn't help in those cases, and brings
in a whole load of new complexity.

   Most people should be able to compile the library and program under
Unix straight out-of-the-box, so to speak, especially if you have a
version of GNU C available.

   There are a couple of `__inline__' directives in the code.  GNU C
(`gcc') should be able to handle them.  If you're not using GNU C, your
C compiler shouldn't see them at all.  If your compiler does, for some
reason, see them and doesn't like them, just `#define' `__inline__' to
be `/* */'.  One easy way to do this is to compile with the flag
`-D__inline__=', which should be understood by most Unix compilers.

   If you still have difficulties, try compiling with the macro
`BZ_STRICT_ANSI' defined.  This should enable you to build the library
in a strictly ANSI compliant environment.  Building the program itself
like this is dangerous and not supported, since you remove `bzip2''s
checks against compressing directories, symbolic links, devices, and
other not-really-a-file entities.  This could cause filesystem
corruption!

   One other thing: if you create a `bzip2' binary for public
distribution, please try and link it statically (`gcc -s').  This
avoids all sorts of library-version issues that others may encounter
later on.

   If you build `bzip2' on Win32, you must set `BZ_UNIX' to 0 and
`BZ_LCCWIN32' to 1, in the file `bzip2.c', before compiling.  Otherwise
the resulting binary won't work correctly.

Reporting bugs
==============

   I tried pretty hard to make sure `bzip2' is bug free, both by design
and by testing.  Hopefully you'll never need to read this section for
real.

   Nevertheless, if `bzip2' dies with a segmentation fault, a bus error
or an internal assertion failure, it will ask you to email me a bug
report.  Experience with version 0.1 shows that almost all these
problems can be traced to either compiler bugs or hardware problems.
   * Recompile the program with no optimisation, and see if it works.
     And/or try a different compiler.  I heard all sorts of stories
     about various flavours of GNU C (and other compilers) generating
     bad code for `bzip2', and I've run across two such examples myself.

     2.7.X versions of GNU C are known to generate bad code from time
     to time, at high optimisation levels.  If you get problems, try
     using the flags `-O2' `-fomit-frame-pointer'
     `-fno-strength-reduce'.  You should specifically *not* use
     `-funroll-loops'.

     You may notice that the Makefile runs four tests as part of the
     build process.  If the program passes all of these, it's a pretty
     good (but not 100%) indication that the compiler has done its job
     correctly.

   * If `bzip2' crashes randomly, and the crashes are not repeatable,
     you may have a flaky memory subsystem.  `bzip2' really hammers
     your memory hierarchy, and if it's a bit marginal, you may get
     these problems.  Ditto if your disk or I/O subsystem is slowly
     failing.  Yup, this really does happen.

     Try using a different machine of the same type, and see if you can
     repeat the problem.

   * This isn't really a bug, but ... If `bzip2' tells you your file is
     corrupted on decompression, and you obtained the file via FTP,
     there is a possibility that you forgot to tell FTP to do a binary
     mode transfer.  That absolutely will cause the file to be
     non-decompressible.  You'll have to transfer it again.

   If you've incorporated `libbzip2' into your own program and are
getting problems, please, please, please, check that the parameters you
are passing in calls to the library, are correct, and in accordance
with what the documentation says is allowable.  I have tried to make
the library robust against such problems, but I'm sure I haven't
succeeded.

   Finally, if the above comments don't help, you'll have to send me a
bug report.  Now, it's just amazing how many people will send me a bug
report saying something like
        bzip2 crashed with segmentation fault on my machine
   and absolutely nothing else.  Needless to say, a such a report is
*totally, utterly, completely and comprehensively 100% useless; a waste
of your time, my time, and net bandwidth*.  With no details at all,
there's no way I can possibly begin to figure out what the problem is.

   The rules of the game are: facts, facts, facts.  Don't omit them
because "oh, they won't be relevant".  At the bare minimum:
        Machine type.  Operating system version.
        Exact version of `bzip2' (do `bzip2 -V').
        Exact version of the compiler used.
        Flags passed to the compiler.
   However, the most important single thing that will help me is the
file that you were trying to compress or decompress at the time the
problem happened.  Without that, my ability to do anything more than
speculate about the cause, is limited.

   Please remember that I connect to the Internet with a modem, so you
should contact me before mailing me huge files.

Did you get the right package?
==============================

   `bzip2' is a resource hog.  It soaks up large amounts of CPU cycles
and memory.  Also, it gives very large latencies.  In the worst case,
you can feed many megabytes of uncompressed data into the library before
getting any compressed output, so this probably rules out applications
requiring interactive behaviour.

   These aren't faults of my implementation, I hope, but more an
intrinsic property of the Burrows-Wheeler transform (unfortunately).
Maybe this isn't what you want.

   If you want a compressor and/or library which is faster, uses less
memory but gets pretty good compression, and has minimal latency,
consider Jean-loup Gailly's and Mark Adler's work, `zlib-1.1.2' and
`gzip-1.2.4'.  Look for them at `http://www.cdrom.com/pub/infozip/zlib'
and `http://www.gzip.org' respectively.

   For something faster and lighter still, you might try Markus F X J
Oberhumer's `LZO' real-time compression/decompression library, at
`http://wildsau.idv.uni-linz.ac.at/mfx/lzo.html'.

   If you want to use the `bzip2' algorithms to compress small blocks
of data, 64k bytes or smaller, for example on an on-the-fly disk
compressor, you'd be well advised not to use this library.  Instead,
I've made a special library tuned for that kind of use.  It's part of
`e2compr-0.40', an on-the-fly disk compressor for the Linux `ext2'
filesystem.  Look at `http://www.netspace.net.au/~reiter/e2compr'.

Testing
=======

   A record of the tests I've done.

   First, some data sets:
   * B: a directory containing 6001 files, one for every length in the
         range 0 to 6000 bytes.  The files contain random lowercase
       letters.  18.7 megabytes.

   * H: my home directory tree.  Documents, source code, mail files,
       compressed data.  H contains B, and also a directory of
     files designed as boundary cases for the sorting; mostly very
     repetitive, nasty files.  565 megabytes.

   * A: directory tree holding various applications built from source:
         `egcs', `gcc-2.8.1', KDE, GTK, Octave, etc.        2200
     megabytes.  The tests conducted are as follows.  Each test means
compressing (a copy of) each file in the data set, decompressing it and
comparing it against the original.

   First, a bunch of tests with block sizes and internal buffer sizes
set very small, to detect any problems with the blocking and buffering
mechanisms.  This required modifying the source code so as to try to
break it.
  1. Data set H, with       buffer size of 1 byte, and block size of 23
     bytes.

  2. Data set B, buffer sizes 1 byte, block size 1 byte.

  3. As (2) but small-mode decompression.

  4. As (2) with block size 2 bytes.

  5. As (2) with block size 3 bytes.

  6. As (2) with block size 4 bytes.

  7. As (2) with block size 5 bytes.

  8. As (2) with block size 6 bytes and small-mode decompression.

  9. H with buffer size of 1 byte, but normal block       size (up to
     900000 bytes).
        Then some tests with unmodified source code.
  1. H, all settings normal.

  2. As (1), with small-mode decompress.

  3. H, compress with flag `-1'.

  4. H, compress with flag `-s', decompress with flag `-s'.

  5. Forwards compatibility: H, `bzip2-0.1pl2' compressing,
     `bzip2-0.9.5' decompressing, all settings normal.

  6. Backwards compatibility:  H, `bzip2-0.9.5' compressing,
     `bzip2-0.1pl2' decompressing, all settings normal.

  7. Bigger tests: A, all settings normal.

  8. As (7), using the fallback (Sadakane-like) sorting algorithm.

  9. As (8), compress with flag `-1', decompress with flag       `-s'.

 10. H, using the fallback sorting algorithm.

 11. Forwards compatibility: A, `bzip2-0.1pl2' compressing,
     `bzip2-0.9.5' decompressing, all settings normal.

 12. Backwards compatibility:  A, `bzip2-0.9.5' compressing,
     `bzip2-0.1pl2' decompressing, all settings normal.

 13. Misc test: about 400 megabytes of `.tar' files with       `bzip2'
     compiled with Checker (a memory access error        detector, like
     Purify).

 14. Misc tests to make sure it builds and runs ok on non-Linux/x86
      platforms.
        These tests were conducted on a 225 MHz IDT WinChip machine,
running Linux 2.0.36.  They represent nearly a week of continuous
computation.  All tests completed successfully.

Further reading
===============

   `bzip2' is not research work, in the sense that it doesn't present
any new ideas.  Rather, it's an engineering exercise based on existing
ideas.

   Four documents describe essentially all the ideas behind `bzip2':
     Michael Burrows and D. J. Wheeler:
       "A block-sorting lossless data compression algorithm"
        10th May 1994.
        Digital SRC Research Report 124.
        ftp://ftp.digital.com/pub/DEC/SRC/research-reports/SRC-124.ps.gz
        If you have trouble finding it, try searching at the
        New Zealand Digital Library, http://www.nzdl.org.

     Daniel S. Hirschberg and Debra A. LeLewer
       "Efficient Decoding of Prefix Codes"
        Communications of the ACM, April 1990, Vol 33, Number 4.
        You might be able to get an electronic copy of this
           from the ACM Digital Library.

     David J. Wheeler
        Program bred3.c and accompanying document bred3.ps.
        This contains the idea behind the multi-table Huffman
        coding scheme.
        ftp://ftp.cl.cam.ac.uk/users/djw3/

     Jon L. Bentley and Robert Sedgewick
       "Fast Algorithms for Sorting and Searching Strings"
        Available from Sedgewick's web page,
        www.cs.princeton.edu/~rs
   The following paper gives valuable additional insights into the
algorithm, but is not immediately the basis of any code used in bzip2.
     Peter Fenwick:
        Block Sorting Text Compression
        Proceedings of the 19th Australasian Computer Science Conference,
          Melbourne, Australia.  Jan 31 - Feb 2, 1996.
        ftp://ftp.cs.auckland.ac.nz/pub/peter-f/ACSC96paper.ps
   Kunihiko Sadakane's sorting algorithm, mentioned above, is available
from:
     http://naomi.is.s.u-tokyo.ac.jp/~sada/papers/Sada98b.ps.gz
   The Manber-Myers suffix array construction algorithm is described in
a paper available from:
     http://www.cs.arizona.edu/people/gene/PAPERS/suffix.ps